\n\tThe main predicates are bb_min/3, bb_min/6 and, as a shorthand,\n\tminimize/2.\n\t
\n\tNote on the treatment of bounded reals: The library allows the cost\n\tto be instantiated to a number of type breal. This is useful e.g.\n\twhen using lib(ic) to solve problems with continuous variables.\n\tWhen the variable domains have been narrowed sufficiently, the\n\tproblem variables (in particular the cost variable) should be\n\tinstantiated to a bounded real, e.g. using the following idiom:\n\t
\n\t\tX is breal_from_bounds(get_min(X),get_max(X))\n\t\n\tBounded reals contain some uncertainty about their true value. If\n\tthis uncertainty is too large, the branch-and-bound procedure may\n\tnot be able to compare the quality of two solutions. In this case,\n\ta warning is issued and the search terminated prematurely. The\n\tproblem can be solved by increasing the delta-parameter, or by\n\tlocating the cost value more precisely.\n\t")). :- comment(bb_cost / 2, [summary : "Low-level primitive for building branch-and-bound-style search procedures", template : "bb_cost(++Handle, -Cost)", see_also : [bb_probe / 7]]). :- comment(bb_finish / 1, [summary : "Low-level primitive for building branch-and-bound-style search procedures", template : "bb_finish(++Handle)", see_also : [bb_probe / 7]]). :- comment(bb_init / 2, [summary : "Low-level primitive for building branch-and-bound-style search procedures", template : "bb_init(++ExtremeCost, -Handle)", see_also : [bb_probe / 7]]). :- comment(bb_min / 3, [summary : "Find a minimal solution using the branch-and-bound method", see_also : [bb_min / 6], desc : html("\tA solution of the goal Goal is found that minimizes\n\tthe value of Cost. Cost should be a\n\tvariable that is affected, and eventually instantiated, by\n\tGoal. Usually, Goal is the search procedure\n\tof a constraint problem and Cost is the variable\n\trepresenting the cost. The solution is found using the branch\n\tand bound method: as soon as a solution is found, it gets\n\tremembered and the search is continued or restarted with an\n\tadditional constraint on the Cost variable which\n\trequires the next solution to be better than the previous one. \n\tIterating this process yields an optimal solution in the end.\n\t
\n\tThe possible options are\n\t
\n\tbb_options{strategy:dichotomic, timeout:60}\n\t\n\tIn order to maximize instead of minimizing, introduce a negated\n\tcost variable in your model and minimize that instead.\n\t\n\tCompatibility note: For backward compatibility, the report_success and\n\treport_failure options also accept Name/Arity specifications with\n\tmaximum arity 3 for the handler goals. The three optional arguments\n\tare then Cost, Handle, and Module.\n\t"), args : ["Goal" : "The (nondeterministic) search goal", "Cost" : "A (usually numeric domain) variable representing the cost", "Options" : "A bb_options structure or variable"], amode : bb_min(+, ?, ?), eg : "\n?- bb_min(member(X,[9,6,8,4,7,2,4,7]), X, O).\nFound a solution with cost 9\nFound a solution with cost 6\nFound a solution with cost 4\nFound a solution with cost 2\nFound no solution with cost -1.0Inf .. 1\nX = 2\nO = bb_options(continue, -1.0Inf, 1.0Inf, 1, 1, 0, 0, _, _)\nyes.\n\n[eclipse 6]: bb_min(member(X,[9,6,8,4,7,2,4,7]), X, bb_options{delta:4}).\nFound a solution with cost 9\nFound a solution with cost 4\nFound no solution with cost -1.0Inf .. 0\nX = 4\nyes.\n\n[eclipse 10]: bb_min(member(X,[99,60,80,40,70,30,70]), X,\n\tbb_options{strategy:dichotomic, from:0}).\nFound a solution with cost 99\nFound a solution with cost 40\nFound no solution with cost 0.0 .. 20.0\nFound a solution with cost 30\nFound no solution with cost 20.0 .. 25.0\nFound no solution with cost 25.0 .. 27.5\nFound no solution with cost 27.5 .. 28.75\nFound no solution with cost 28.75 .. 29.0\n\nX = 30\nyes.\n"]). :- comment(bb_min / 6, [summary : "Find a minimal solution using the branch-and-bound method", see_also : [bb_min / 3], desc : html("\tA solution of the goal Goal is found that minimizes\n\tthe value of Cost. Cost should be a\n\tvariable that is affected, and eventually instantiated, by\n\tGoal. Usually, Goal is the search procedure\n\tof a constraint problem and Cost is the variable\n\trepresenting the cost. The solution is found using the branch\n\tand bound method: as soon as a solution is found, it gets\n\tremembered and the search is continued or restarted with an\n\tadditional constraint on the Cost variable which\n\trequires the next solution to be better than the previous one. \n\tIterating this process yields an optimal solution in the end.\n\t
\n\tThe possible options are\n\t
\n\tbb_options{strategy:dichotomic, timeout:60}\n\t\n\tIn order to maximize instead of minimizing, introduce a negated\n\tcost variable in your model and minimize that instead.\n\t\n\tUnlike bb_min/3, bb_min/6 does not affect Goal or Cost after\n\tthe optimum has been found. Instead, the optimum cost value is returned\n\tin Optimum, and the Solution argument gets unified with an instance of\n\tTemplate where the variables have the values that correspond to the\n\toptimal solution. Note that bb_min/3 is actually based on bb_min/6\n\tand can be defined as:\n\t
\n\tbb_min(Goal, Cost, Options) :-\n\t bb_min(Goal, Cost, Goal, Goal, Cost, Options).\n\t\n\t
\n\tCompatibility note: For backward compatibility, the report_success and\n\treport_failure options also accept Name/Arity specifications with\n\tmaximum arity 3 for the handler goals. The three optional arguments\n\tare then Cost, Handle, and Module.\n\t"), args : ["Goal" : "The (nondeterministic) search goal", "Cost" : "A (usually numeric domain) variable representing the cost", "Template" : "A term containing all or some problem variables", "Solution" : "A term which will be unified with the optimized Template", "Optimum" : "A variable which will be set to the optimum value of Cost", "Options" : "A bb_options structure or variable"], amode : bb_min(+, ?, ?, ?, ?, ?)]). :- comment(bb_probe / 7, [summary : "Low-level primitive for building branch-and-bound-style search procedures", template : "bb_probe(++From, ++To, +Goal, ?Template, ?Cost, ++Handle, ++Module)", desc : html("\n\tbb_probe tries to find a solution for Goal in the range From..To.\n\tIf there is a solution, its Template and Cost are stored in Handle,\n\tthe computation is undone, and bb_probe succeeds.\n\tIf there is no solution, Handle is not changed and bb_probe fails.\n\tThe primitive set_var_bounds/3 is used to impose cost bounds\n\tduring the search process in a generic way."), see_also : [bb_init / 2, bb_cost / 2, bb_solution / 2, bb_finish / 1, bb_min / 3, bb_min / 4, set_var_bounds / 3], eg : "% a simple branch-and-bound procedure\nmy_minimize(Goal, Cost, Solution, OptCost, Module) :-\n\tbb_init(1000000, Handle),\n\t(\n\t bb_delta(0, 1000000, Goal, Cost, Handle, Module)\n\t;\n\t bb_solution(Handle, Solution),\n\t bb_cost(Handle, OptCost)\n\t),\n\tbb_finish(Handle).\n\nbb_delta(From, To, Goal, Cost, Handle, Module) :-\n\tbb_probe(From, To, Goal, Goal, Cost, Handle, Module),\n\tNewTo is bb_cost(Handle) - 1,\n\tbb_delta(From, NewTo, Goal, Cost, Handle, Module).\n "]). :- comment(bb_solution / 2, [summary : "Low-level primitive for building branch-and-bound-style search procedures", template : "bb_solution(++Handle, -Solution)", see_also : [bb_probe / 7]]). :- comment(minimize / 2, [summary : "Find a minimal solution using the branch-and-bound method", desc : html("This is a shorthand for\n \t
\n\tbb_min(+Goal, ?Cost, _DefaultOptions)\n\t\n\tSee bb_min/3 for details."), template : "minimize(+Goal, ?Cost)", see_also : [bb_min / 3]]). :- comment(minimize / 3, hidden). :- comment(bb_min / 7, hidden). :- comment(bb_min / 4, hidden).